package arithmetic;

import java.util.Random;

public class Subsequence {

	static int max(int i1, int i2, int i3) {
		if (i1 > i2) {
			return i1 > i3 ? i1 : i3;
		} else {
			return i2 > i3 ? i2 : i3;
		}
	}

	// 动态规划
	static int recursion2(int[] a) {
		int sum = a[0];
		int isum = a[0];
		for (int i = 1; i < a.length; i++) {
			if (isum <= 0) {
				isum = a[i];
			} else {
				isum += a[i];
			}
			if (sum < isum) {
				sum = isum;
			}
		}

		return sum;
	}

	static int recursion(int[] a, int left, int right) {

		if ((right - left + 1) == 2) {
			return max(a[left], a[right], a[left] + a[right]);
		}
		if (right == left) {
			return a[left];
		}

		int m = (right + left) / 2;
		int sum = 0;
		int sumLeft = a[m];
		int sumRight = a[m + 1];
		int tmp = 0;
		for (int i = m; i >= left; i--) {
			tmp = tmp + a[i];
			if (tmp > sumLeft) {
				sumLeft = tmp;
			}
		}
		// System.out.println("左侧最大:" + sumLeft);
		tmp = 0;
		for (int i = m + 1; i <= right; i++) {
			tmp = tmp + a[i];
			if (tmp > sumRight) {
				sumRight = tmp;
			}
		}
		// System.out.println("右侧最大:" + sumRight);
		sum = sumLeft + sumRight;
		// System.out.println("最大值:" + sum);

		return max(recursion(a, left, m), sum, recursion(a, m + 1, right));
	}

	public static void main(String[] args) {
		int[] a = { 4, 3, -6, -2, -21, 1 };
		System.out.println("----------------" + recursion(a, 0, a.length - 1));
		System.out.println(recursion2(a));
		int[] b = { 9, -2, 1, 10 };
		System.out.println("----------------" + recursion(b, 0, b.length - 1));
		System.out.println(recursion2(b));
		int[] c = { 2, 1, -6 };
		System.out.println("----------------" + recursion(c, 0, c.length - 1));
		System.out.println(recursion2(c));
		int[] d = new int[1000];
		for (int i = 0; i < d.length; i++) {
			Random random = new Random();
			d[i] = random.nextInt(11) * (random.nextInt(2) == 0 ? -1 : 1);
			System.out.println(d[i]);
		}

		long start = System.nanoTime();
		System.out.println("----------------" + recursion(d, 0, d.length - 1));
		long start2 = System.nanoTime();
		System.out.println("动态规划" + recursion2(d));
		long start3 = System.nanoTime();
		System.out.println(start2 - start);
		System.out.println(start3 - start2);

	}
}
